import treeUnit from '../unit/TreeUnit.js'

function TreeCode() {
    var tree = null
    let TreeNode = function (value) {
        this.key = value;
        this.left = null;
        this.right = null;
    }

    this.createTree = function () {
        this.insert(3)
        this.insert(2)
        this.insert(1)
        this.insert(8)
        this.insert(6)
        this.insert(5)
        this.insert(7)
        this.insert(10)
        this.insert(9)
        this.insert(11)
        return tree;
    }

    this.createTreeArray = () => {
        //前序遍历
        function NLR(biTree, index) {
            if (biTree === null) return;
            treeArray[index] = biTree.key + ''
            NLR(biTree.left, 2 * index + 1);
            NLR(biTree.right, 2 * index + 2);
        }
        let treeArray = []
        NLR(tree, 0)
        return treeArray
    }
    /**
     * 插入
     * @param {number} key 结点的键值
     */
     this.insert = function (key) {
        function insert(tree) {
            if (!tree) {
                return new TreeNode(key);
            }
            if (key <= tree.key) {
                tree.left = insert(tree.left)
            } else {
                tree.right = insert(tree.right)
            }
            return tree
        }   
        tree = insert(tree)
    }
    /**
     * 查询
     * @param {number} tree 结点的键值
     * @returns 查询结果，若查到返回
     */
    function search(key) {
        function search(tree) {
            if (tree) {
                if (tree.key === key) {
                    return tree
                } else if (key < tree.key) {
                    return search(tree.left)
                } else {
                    return search(tree.right)
                }
            }
        }
        return search(tree)
    }
    /**
     * 删除
     * @param {number} tree 结点的键值
     */
    function deleteNode(key) {
        function deleteNode(tree, key) {
            if (tree) {
                if (tree.key === key) {
                    if (tree.left && tree.right) {
                        var minKey = minNode(tree.right).key
                        tree.key = minKey
                        tree.right = deleteNode(tree.right, minKey)
                    } else if (tree.left) {
                        return tree.left
                    } else if (tree.right) {
                        return tree.right
                    } else {
                        return null
                    }
                } else if (key < tree.key) {
                    tree.left = deleteNode(tree.left, key)
                } else {
                    tree.right = deleteNode(tree.right, key)
                }
                return tree
            }
        }
        deleteNode(tree, key)
    }

    function minNode(tree) {
        if (!tree) {
            console.log("not find")
        } else if (tree.left) {
            return minNode(tree.left)
        } else {
            return tree
        }
    }

    this.search = (key) => {
        var result = search(key)
        return result === undefined ? -1 : result.key
    }

    this.delete = (key) => {
        deleteNode(key)
    }
}

var tree = new TreeCode();
tree.createTree()
treeUnit.printTree(tree.createTreeArray())
console.log("查找结果：" + tree.search(8))
tree.delete(8)
console.log("删除结点: 8")
treeUnit.printTree(tree.createTreeArray())
console.log("查找结果：" + tree.search(8))

